package _go

/*322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。



示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2


提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
通过次数328,594提交次数735,343*/

//这个问题属于 背包问题中的  完全背包问题  因为物品数量是无限的
//时间复杂度 O(nm) n是金币的种类 m是金额
//空间复杂度 O(m) 需要开辟一个amout的dp数组

func coinChange(coins []int, amount int) int {
	wt := len(coins)
	if wt <= 0 || amount < 0 {
		return -1
	}

	//定义  价值为i的时候数量最小个数 dp[i]
	dp := make([]int, amount+1)

	//初始化成最大值
	for i := 1; i <= amount; i++ {
		dp[i] = math.MaxInt32
	}

	//外层是硬币的种类 因为是完全背包问题 没有数量限制 只有种类
	for i := 0; i < wt; i++ {
		//内层是 金额遍历  从金额为0 开始遍历 自下而上的过程
		//这个题是 有面值要求的  所以金额可以从数额的第一个值开始 去掉没有用的遍历
		for j := coins[i]; j <= amount; j++ {
			if dp[j-coins[i]] != math.MaxInt32 {
				//动规数组的状态只跟前一个的状态有关  要么是保持一致， 要么是上一个的数量加一
				dp[j] = min(dp[j], dp[j-coins[i]]+1)
			}
		}
	}
	//如果最后没有找到就返回-1
	if dp[amount] == math.MaxInt32 {
		return -1
	}

	return dp[amount]

}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
